package 环行链表;

import 翻转链表.Demo206;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 环形链表, 快慢指针判断是否有环，然后再去找相遇的位置。数学证明 x=z,
 * 即相遇点开始走慢指针与起始点走慢指针，一定在入口相遇
 * @date 2022/10/15 15:59
 */
public class Demo142 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode detectCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        ListNode pos=head;
        //快慢指针判断是否有环
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            //有环的话肯定存在相遇
            if(slow==fast){
                //相遇，头指针和慢指针开始走动，相遇点即为环入口点
                while (pos!=slow){
                    pos=pos.next;
                    slow=slow.next;
                }
                return pos;
            }
        }
      return null;
    }
}
